package com.jhy.review.day05;

import com.jhy.review.day04.Graph;
import com.jhy.review.day04.Node;

import java.util.*;

/**
 * 2022年7月25日21:30:43
 * 拓扑排序算法
 * 适用范围：要求有向图，且有入度为0的节点，且没有环
 *  该思想是：
 *  有一个入度为0的节点
 *  hashmap当中存放着的是每一个节点的入度的数量
 *  队列当中存放这的是入度为0的节点
 *  我们还有申请一个集合 来存放拓扑排序的顺序
 *
 *  从入度为0的节点出发，入度为0就放在队列当中 然后弹出增加到集合里面去，每一次弹出就把当前节点的nexts的入度减1.
 */
public class TopologySort {

    public List<Node> topologySort(Graph graph){
        // 存放的是节点的入度的数量
        HashMap<Node, Integer> hashMapIn = new HashMap<>();
        // 存放的是入度为0的节点的数量
        Queue<Node> queue = new LinkedList<>();
        for(Node node : graph.nodes.values()){
            // key为节点 node.in 为入度的数量
            hashMapIn.put(node,node.in);
            // 如果节点的入度数量为0的话
            if(node.in == 0){
                // 队列添加
                queue.add(node);
            }
        }
        // 存放弹出的节点 保持顺序
        List<Node> list = new ArrayList<>();

        // 遍历队列
        while (!queue.isEmpty()){
            // 弹出这个节点
            Node poll = queue.poll();
            list.add(poll);
            // 算出这个节点当中下一个节点们，使下一节点们的入度减一，也就是当前弹出来的节点与其他节点断开
            for(Node next : poll.nexts){
                hashMapIn.put(next,hashMapIn.get(next)-1);
                // 一旦发现当前节点的入度为0就加在队列当中去。
                if(hashMapIn.get(next) == 0){
                    queue.add(next);
                }
            }

        }
        return list;
    }

}
